package queue

import "fmt"

type node struct {
	val  interface{}
	next *node
}

// 链表环形队列

func NewNodeCircular(n int) *node {
	head := &node{
		val:  0,
		next: nil,
	}
	cur := head
	for i := 1; i < n; i++ {
		tmp := &node{
			val:  i,
			next: nil,
		}
		cur.next = tmp
		cur = tmp
		if i == n-1 {
			tmp.next = head
		}
	}

	return head
}

type CircularQueueOnLinkedList struct {
	headNode *node
	tailNode *node
	capacity int
	head     int
	tail     int
}

func NewCircularQueueOnLinkedList(n int) *CircularQueueOnLinkedList {
	if n <= 0 {
		return nil
	}
	head := NewNodeCircular(n)
	return &CircularQueueOnLinkedList{
		head,
		head,
		n,
		0,
		0,
	}
}

func (that *CircularQueueOnLinkedList) IsEmpty() bool {
	if that.head == that.tail {
		return true
	}
	return false
}

func (that *CircularQueueOnLinkedList) IsFull() bool {
	if that.head == (that.tail+1)%that.capacity {
		return true
	}
	return false
}

func (that *CircularQueueOnLinkedList) EnQueue(v interface{}) bool {
	if that.IsFull() {
		return false
	}
	that.tailNode.val = v
	that.tailNode = that.tailNode.next
	that.tail = (that.tail + 1) % that.capacity
	return true
}

func (that *CircularQueueOnLinkedList) DeQueue() interface{} {
	if that.IsEmpty() {
		return nil
	}
	v := that.headNode.val
	that.headNode = that.headNode.next
	that.head = (that.head + 1) % that.capacity
	return v
}

func (that *CircularQueueOnLinkedList) Print() string {
	if that.IsEmpty() {
		return "empty queue"
	}
	result := "head"
	var i = that.head
	var node = that.headNode
	for {
		result += fmt.Sprintf("<-%+v", node.val)
		i = (i + 1) % that.capacity
		if i == that.tail {
			break
		}
		node = node.next
	}
	result += "<-tail"
	return result
}
